/**
 * 链表实现栈
 */
#include <iostream>
#include <stdexcept>

using namespace std;

// 栈内元素定制化，模板实现
template <typename T>
class Stack
{
    // 链表节点结构体
    struct Node
    {
        T data;
        Node *next;
        Node(T d) : data(d), next(nullptr) {}
        Node(T d, Node *p) : data(d), next(p) {}
    };

private:
    Node *head; // 头节点
    int size;   // 元素个数

public:
    Stack() : head(nullptr), size(0) {}
    ~Stack();

    // 入
    void push(T element);
    // 出
    T pop();
    // 获取栈顶元素
    T top() const;
    // 获取元素个数
    int getSize() const;
};

template <typename T>
Stack<T>::~Stack()
{
    while (head)
    {
        Node *temp = head;
        head = head->next;
        delete temp;
    }
}

template <typename T>
void Stack<T>::push(T element)
{
    Node *newNode = new Node(element, head);
    head = newNode;
    ++size;
}

template <typename T>
T Stack<T>::pop()
{
    if (head == nullptr)
    {
        throw std::underflow_error("Stack is empty");
    }
    T temp = head->data;
    Node *pDel = head;
    head = head->next;
    delete pDel;
    size--;
    return temp;
}

template <typename T>
T Stack<T>::top() const
{
    if (head == nullptr)
    {
        throw std::underflow_error("Stack is empty");
    }
    return head->data;
}

template <typename T>
int Stack<T>::getSize() const
{
    return size;
}

int main()
{
    Stack<int> st;
    st.push(4);
    st.push(33);
    st.push(16);
    st.push(78);
    st.push(15);
    cout << st.top() << endl;
    cout << st.getSize() << endl;
    st.pop();
    cout << st.top() << endl;
    cout << st.getSize() << endl;
    st.pop();
    cout << st.top() << endl;
    cout << st.getSize() << endl;
}